{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LFM 梯度下降算法实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 引入依赖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据准备"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R = np.array([[4,0,2,0,1],\n",
    "             [0,2,3,0,0],\n",
    "             [1,0,2,4,0],\n",
    "             [5,0,0,3,1],\n",
    "             [0,0,1,5,1],\n",
    "             [0,3,2,4,1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "@输入参数：\n",
    "R: M*N 的评分矩阵\n",
    "K: 隐特征向量维度\n",
    "max_iter: 最大迭代次数\n",
    "alpha: 步长\n",
    "lamda: 正则化系数\n",
    "\n",
    "@输出：\n",
    "分解之后的P, Q\n",
    "P: 初始化用户特征矩阵M*K\n",
    "Q: 初始化物品特征矩阵K*M\n",
    "\"\"\"\n",
    "\n",
    "# 给定超参数\n",
    "\n",
    "K = 2\n",
    "max_iter = 5000\n",
    "alpha = 0.0002\n",
    "lamda = 0.004\n",
    "    \n",
    "# 核心算法\n",
    "def LFM_grad_desc(R, k=2, max_iter=1000, alpha=0.0001, lamda=0.002):\n",
    "    # 基本维度信息\n",
    "    M = len(R)\n",
    "    N = len(R[0])\n",
    "    \n",
    "    # P, Q 随机生成初始化\n",
    "    P = np.random.rand(M, K)\n",
    "    Q = np.random.rand(N, K)\n",
    "    Q = Q.T\n",
    "    \n",
    "    # 开始迭代\n",
    "    for step in range(max_iter):\n",
    "        # 对所有的用户u, 物品i做遍历，对应的特征向量Pu, Qi 梯P度下降\n",
    "        for u in range(M):\n",
    "            for i in range(N):\n",
    "                # 对每一个大于0的评分，求出预测评分误差\n",
    "                if R[u][i] > 0:\n",
    "                    eui = np.dot(P[u,:], Q[:,i]) - R[u][i]\n",
    "                    \n",
    "                    # 代入公式，按照梯度下降算法更新当前的Pu, Qi\n",
    "                    for k in range(K):\n",
    "                        P[u][k] = P[u][k] - alpha * ( 2 * eui * Q[k][i] + 2 * lamda * P[u][k] )\n",
    "                        Q[k][i] = Q[k][i] - alpha * ( 2 * eui * P[u][k] + 2 * lamda * Q[k][i] )\n",
    "        # u, i 遍历完成，所有特征向量更新完成，可以得到P, Q, 可以计算预测评分矩阵\n",
    "        predR = np.dot(P, Q)\n",
    "        \n",
    "        # 计算当前损失函数\n",
    "        cost = 0\n",
    "        for u in range(M):\n",
    "            for i in range(N):\n",
    "                if R[u][i] > 0:\n",
    "                    cost += ( np.dot(P[u,:], Q[:,i]) - R[u][i]) ** 2\n",
    "                    # 加上正则化项\n",
    "                    for k in range(K):\n",
    "                        cost += lamda * (P[u][k] ** 2 + Q[k][i] ** 2)\n",
    "        \n",
    "        if cost < 0.0001:\n",
    "            break\n",
    "                        \n",
    "    return P, Q.T, cost\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.41902008  1.61473653]\n",
      " [ 0.65936571  1.71902197]\n",
      " [ 1.44162577  0.61418301]\n",
      " [-0.03316578  2.03988991]\n",
      " [ 1.79063136  0.50840057]\n",
      " [ 0.97109256  1.35376491]]\n",
      "[[-0.25204215  2.46099516]\n",
      " [ 1.2358566   0.94597583]\n",
      " [ 0.47191868  1.28585006]\n",
      " [ 2.24132937  1.48142149]\n",
      " [ 0.3949018   0.49589823]]\n",
      "1.97168190259086\n",
      "[[4 0 2 0 1]\n",
      " [0 2 3 0 0]\n",
      " [1 0 2 4 0]\n",
      " [5 0 0 3 1]\n",
      " [0 0 1 5 1]\n",
      " [0 3 2 4 1]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[3.86824807, 2.04535046, 2.27405248, 3.33126741, 0.96621677],\n",
       "       [4.06431681, 2.4410347 , 2.52157151, 4.02445183, 1.11284465],\n",
       "       [1.14815097, 2.36264501, 1.4700774 , 4.1410221 , 0.87387288],\n",
       "       [5.02851837, 1.8886984 , 2.60734102, 2.94760131, 0.99848056],\n",
       "       [0.79985676, 2.69389824, 1.49875929, 4.76655019, 0.95923849],\n",
       "       [3.08685263, 2.48076003, 2.19901541, 4.1820347 , 1.05481582]])"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P, Q, cost = LFM_grad_desc(R, K, max_iter, alpha, lamda)\n",
    "\n",
    "print(P)\n",
    "print(Q)\n",
    "print(cost)\n",
    "\n",
    "predR = P.dot(Q.T)\n",
    "print(R)\n",
    "predR\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
